package com.singzi.leetcode.N100;

import java.util.ArrayList;

public class T0079 {
    public static void main(String[] args) {
        char[][] board = {
            {'A', 'B', 'C', 'E'},
            {'S', 'F', 'C', 'S'},
            {'A', 'D', 'E', 'E'}};
//        char [][]board = {{'a'}};
        Solution0079 solution0079 = new Solution0079();
        System.out.println(solution0079.exist(board, "ABCESCFSA"));

    }
}
class Solution0079 {

    private  ArrayList<int[]> wordList = new ArrayList<>();
//    private HashMap<>
    private boolean flag = false;
    public boolean exist(char[][] board, String word) {
        if(word.length()==0||word.length()==1&&board.length==1&&board[0].length==1&&board[0][0]==word.charAt(0)) return true;

        int [][]visited = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int sum = 0;
                addWord(board, visited,  i, j, word, sum);
                if(flag) {
                    return true;
                }

                
            }
        }
        return false;
    }
    public void addWord(char[][] board, int [][]visited, int col, int row, String word, int sum){

        if(sum == word.length()) {
            flag = true;
            return;
        }
        if(!flag&&col > 0&& word.charAt(sum) == board[col-1][row]&&visited[col-1][row]==0){
            visited[col-1][row] = 1;
            addWord(board, visited, col-1, row, word, sum+1);
            visited[col-1][row] = 0;
        }
        if(!flag&&col < board.length-1 && word.charAt(sum) == board[col+1][row]&&visited[col+1][row]==0){
            visited[col+1][row] = 1;
            addWord(board, visited, col+1, row, word, sum+1);
            visited[col+1][row] = 0;
        }
        if(!flag&&row > 0&& word.charAt(sum) == board[col][row-1]&&visited[col][row-1]==0){
            visited[col][row-1] = 1;
            addWord(board, visited, col, row-1, word, sum+1);
            visited[col][row-1] = 0;
        }
        if(!flag&&row < board[0].length-1 && word.charAt(sum) == board[col][row+1]&&visited[col][row+1]==0){
            visited[col][row+1] = 1;
            addWord(board, visited, col, row+1, word, sum+1);
            visited[col][row+1] = 0;
        }
    }
}